package com.fang.algorithm.zuo.dp;

/**
 * @author lingxiao.fang
 * @Desc 两个字符串的最长公共子序列
 * @createTime 2025/3/17 16:14
 */
public class Test03_LongestCommonChildStr {

    public static void main(String[] args) {
        String str1 = "abcde";
        String str2 = "ace";
        System.out.println(lcs(str1, str2));
    }

    private static int lcs(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() < 1 || str2.length() < 1) {
            return 0;
        }
        int[][] dp = new int[str1.length()][str2.length()];
        // 填充00位置
        dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
        // 填充第一列
        for (int i = 1; i < str1.length(); i++) {
            dp[i][0] = Math.max(dp[i - 1][0], str1.charAt(i) == str2.charAt(0) ? 1 : 0);
        }
        // 填充第一行
        for (int j = 1; j < str2.length(); j++) {
            dp[0][j] = Math.max(dp[0][j - 1], str1.charAt(0) == str2.charAt(j) ? 1 : 0);
        }
        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp[str1.length() - 1][str2.length() - 1];
    }


}
